package com.hard;

import java.util.Arrays;

/**
 * TODO(1044. 最长重复子串)
 *
 * @author leon
 * @date 2021年12月23日 17:32
 */
public class LongestDupSubstring {
    /**
     * 做不来，先试试暴力
     * @param s
     * @return
     */
    public String longestDupSubstring(String s) {

        int n = s.length();
        String ans = "";
        for (int i = 1; i < n; i++) {
            // 前字符串,不包括i位置的字符
            String ss = s.substring(0,i);
            //
            for (int j = i; j >0 ; j--) {
                String last = s.substring(j,i+1);
                // 换成KMP还超时
                // 表示此法可能不适用
                if (KMP(ss,last)>-1){
                    if(ans.length()<last.length()){
                        ans =last;
                    }
                }
            }
        }
        return ans;

    }

    /**
     * 判断p是否是s的字串,一般匹配法。超时
     * @param s
     * @param p
     * @return
     */
    public int isSubString(String s,String p){
        char[] sarray = s.toCharArray();
        char[] parray = p.toCharArray();
        int i = 0,j=0;
        for (; i<sarray.length&&j<parray.length ; ) {
                if(sarray[i]==parray[j]){
                    i++;
                    j++;
                }else {
                    i = i-j+1;
                    j=0;
                }
        }
        if(j== parray.length){
            return i-j;
        }

        return -1;

    }

    /**
     * KMP字符串匹配算法
     * @param s
     * @param p
     * @return
     */
    public int KMP(String s,String p){
        char[] sarray = s.toCharArray();
        char[] parray = p.toCharArray();
        int[] next = getNext(p);
        int i = 0,j=0;
        while (i<sarray.length&&j< parray.length){
            if(j==-1||sarray[i]==parray[j]){
                i++;
                j++;
            }else {
                j = next[j];
            }

        }

        if(j == p.length()){
            return i-j;
        }else {
            return -1;
        }
    }

    /**
     * 计算next数组
     * @param p
     * @return
     */
    public int[] getNext(String p){
        char[] array = p.toCharArray();
        int[] next = new int[array.length];
        int k = -1;
        next[0] = k;
        int j = 0;
        while (j< array.length-1){
            if(k == -1||array[k] == array[j]){
                    next[++j] = ++k;
            }else {
                k = next[k];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        System.out.println(new LongestDupSubstring().longestDupSubstring("abcda"));
    }
}
